(1) Field of the Invention
The present invention relates to random number generation and in particular to an improved method and apparatus for generating random numbers.
(2) Description of the Art
Random number generation plays a vital role in a wide variety of applications; for example cryptography, numerical simulation and gaming applications. In the field of cryptography, keys are formed using a stream of random numbers and failure to supply numbers that are sufficiently random can seriously compromise the security of the cryptographic system. Furthermore, the most secure cryptographic techniques require random numbers to be supplied at a very high bit rate. For example, in the case of a One Time Pad (OTP) encryption scheme, the number of random bits required is equal to the number of bits of information to be encrypted.
Many different types of random number generator (RNG) have thus been developed over the years to meet the quality (i.e. randomness) and bit rate requirements of the above applications. For example, it is known to use quantum phenomena to provide inherently random number generation. Devices based on the radioactive decay of elements and the randomness associated with the path traveled by single photons of light passing through a beam splitter have thus been developed. Although such devices offer truly random number generation, the associated complexity makes high bit rate, low cost, devices impractical.
Random number generators based on a variety of electrical techniques are also known. However, such devices are typically used in applications where low levels of randomness are acceptable. Two typical examples of electrical RNGs are described in U.S. Pat. No. 5,224,165 and U.S. Pat. No. 6,369,727.
U.S. Pat. No. 5,224,165 describes a low cost random number generator having a plurality of channels in which noise is generated by a pair of diodes. The noise of the two diodes is fed to a comparator and converted into a stream of random binary data bits. A reference noise channel is also provided to output a stream of reference data bits. A exclusive-or (XOR) operation is performed on the random bits produced by each noise channel and the random bits provided by the reference noise channel. In this manner, the relatively low quality of the random binary data bits can be improved. However, the device of U.S. Pat. No. 5,224,165 falls short of both the bit rate and quality (i.e. level of randomness) required for cryptographic applications.
U.S. Pat. No. 6,369,727 describes an alternative RNG in which amplified electrical noise is passed to an analogue to digital converter (ADC). A normal distribution of digital words is output by the ADC and converted to a random number stream using a reductive mapping technique. The complexity of implementing the reductive mapping technique, and the limited speed of the ADC, means that the bit rate attainable from such a RNG is somewhat limited.